package ru.susu.algebra.centralunits.alternating.period;

import java.math.BigInteger;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.apache.commons.lang.ObjectUtils;
import org.apache.log4j.Logger;

import com.google.common.collect.Lists;
import com.google.common.collect.Sets;

import ru.susu.algebra.centralunits.alternating.initializers.LocalUnitsInitializer;
import ru.susu.algebra.centralunits.alternating.initializers.QuadraticFieldsInitializer;
import ru.susu.algebra.field.quadratic.QuadraticFieldGeneralForm;
import ru.susu.algebra.field.quadratic.QuadraticInteger;
import ru.susu.algebra.matrix.NumbersMatrix;
import ru.susu.algebra.pair.Pair;
import ru.susu.algebra.partition.Partition;
import ru.susu.algebra.properties.IPropertySource;
import ru.susu.algebra.util.NumberUtilities;
import ru.susu.algebra.util.NumberWrapperUtilities;
import ru.susu.algebra.wrapper.number.BigIntegerWrapper;

/**
 * @author akargapolov
 * @since: 14.10.2010
 */
public class MatrixPowAlternatingPeriodExtractor implements IAlternatingPeriodExtractor
{
	private static final Logger _log = Logger.getLogger(MatrixPowAlternatingPeriodExtractor.class.getSimpleName());

	public static BigInteger PLAIN_PERIOD_THRESHOLD = BigInteger.valueOf(500);

	private PlainAlternatingPeriodExtractor _plain = new PlainAlternatingPeriodExtractor();

	private static final String INTEGER_PERIOD = MatrixPowAlternatingPeriodExtractor.class.getSimpleName() + "_IntegerPeriod";

	@Override
	public BigInteger getIntegerPeriod(IPropertySource ps, Partition partition, BigInteger mod)
	{
		if (!ps.containsKey(INTEGER_PERIOD))
		{
			ps.setValue(INTEGER_PERIOD, new HashMap<Pair<Partition, BigInteger>, BigInteger>());
		}
		@SuppressWarnings("unchecked")
		Map<Pair<Partition, BigInteger>, BigInteger> map = (Map<Pair<Partition, BigInteger>, BigInteger>) ps
				.getValue(INTEGER_PERIOD);
		Pair<Partition, BigInteger> key = Pair.pair(partition, mod);
		if (!map.containsKey(key))
		{
			//_log.info("getIntegerPeriod - " + partition + " mod " + mod);
			Pair<Integer, Integer> pair = NumberUtilities.factorization(mod)[0];
			int prime = pair.getKey();
			int pow = pair.getValue();
			if (pow == 1)
			{
				return _plain.getIntegerPeriod(ps, partition, mod);
			}
			BigInteger prevPeriod = getIntegerPeriod(ps, partition, mod.divide(BigInteger.valueOf(prime)));
			for (int index = 1; index <= prime; index++)
			{
				BigInteger period = prevPeriod.multiply(BigInteger.valueOf(index));
				NumbersMatrix<BigInteger> vector0 = createVector0(ps, partition, mod);
				NumbersMatrix<BigInteger> vectorn = getVector(ps, partition, period, mod);
				if (ObjectUtils.equals(vector0, vectorn))
				{
					map.put(key, period);
					break;
				}
			}
			_log.info("Period for " + QuadraticFieldsInitializer.getGeneralUnit(ps, partition) + " mod " + mod + " - " + map.get(key));
		}
		if (!map.containsKey(key))
		{
			throw new RuntimeException();
		}
		return map.get(key);
	}

	@Override
	public List<Pair<BigInteger, BigInteger>> getPeriod(IPropertySource ps, Partition partition, BigInteger mod)
	{
		BigInteger period = getIntegerPeriod(ps, partition, mod);
		if (PLAIN_PERIOD_THRESHOLD.compareTo(period) >= 0)
		{
			return _plain.getPeriod(ps, partition, mod);
		}
		return Lists.newArrayList();
	}

	private static final String GOOD_PERIODS = MatrixPowAlternatingPeriodExtractor.class.getSimpleName() + "_GoodPeriods";

	@Override
	public List<Pair<BigInteger, BigInteger>> listGoodPeriods(IPropertySource ps, Partition partition, BigInteger mod)
	{
		if (!ps.containsKey(GOOD_PERIODS))
		{
			ps.setValue(GOOD_PERIODS, new HashMap<Pair<Partition, BigInteger>, List<Pair<BigInteger, BigInteger>>>());
		}
		@SuppressWarnings("unchecked")
		Map<Pair<Partition, BigInteger>, List<Pair<BigInteger, BigInteger>>> map = (Map<Pair<Partition, BigInteger>, List<Pair<BigInteger, BigInteger>>>) ps.getValue(GOOD_PERIODS);
		Pair<Partition, BigInteger> key = Pair.pair(partition, mod);
		if (!map.containsKey(key))
		{
			Pair<Integer, Integer> pair = NumberUtilities.factorization(mod)[0];
			int prime = pair.getKey();
			int pow = pair.getValue();
			if (pow == 1)
			{
				return _plain.listGoodPeriods(ps, partition, mod);
			}
			List<Pair<BigInteger, BigInteger>> prevPeriods = listGoodPeriods(ps, partition, mod.divide(BigInteger.valueOf(prime)));
			BigInteger prevPeriod = getIntegerPeriod(ps, partition, mod.divide(BigInteger.valueOf(prime)));
			BigInteger period = getIntegerPeriod(ps, partition, mod);
			Set<BigInteger> indexes = Sets.newTreeSet();
			for (BigInteger t = BigInteger.ZERO;period.compareTo(t) > 0; t = t.add(prevPeriod))
			{
				indexes.add(t);
			}
			for (Pair<BigInteger, BigInteger> prev : prevPeriods)
			{
				BigInteger index = prev.getKey();
				if (!ObjectUtils.equals(BigInteger.ZERO, index))
				{
					for (BigInteger m = BigInteger.ONE;m.compareTo(period.divide(index)) < 0; m = m.add(BigInteger.ONE))
					{
						indexes.add(m.multiply(index));
					}
				}
			}

			BigInteger alphaC = LocalUnitsInitializer.getAlphaCoefficient(ps, partition).mod(mod);
			BigInteger betaC = LocalUnitsInitializer.getBetaCoefficient(ps, partition).mod(mod);
			QuadraticInteger character = QuadraticFieldsInitializer.getCharacter(ps, partition);
			int bd = character.getB().multiply(character.getD()).intValue();

			List<Pair<BigInteger, BigInteger>> list = Lists.newArrayList();
			for (BigInteger index : indexes)
			{
				NumbersMatrix<BigInteger> vector = getVector(ps, partition, index, mod);
				BigInteger alpha = vector.getValues()[1][0].getValue();
				BigInteger beta = vector.getValues()[1][1].getValue();
				Pair<BigInteger, BigInteger> t = PlainAlternatingPeriodExtractor.calcT(alphaC, betaC, alpha, beta, mod, index, bd);
				if (t != null)
				{
					list.add(t);
					_log.info("T extractor for bd = " + bd + " t = " + t + " for alpha = " + alphaC + " beta = " + betaC);
				}
			}
			map.put(key, list);
		}
		return map.get(key);
	}

	private NumbersMatrix<BigInteger> createMatrix(IPropertySource ps, Partition partition)
	{
		try
		{
			QuadraticFieldGeneralForm unit = QuadraticFieldsInitializer.getGeneralUnit(ps, partition);
			BigIntegerWrapper[][] integers = new BigIntegerWrapper[2][2];
			integers[0][0] = new BigIntegerWrapper(unit.getTrace());
			integers[0][1] = new BigIntegerWrapper(BigInteger.valueOf(-1).multiply(unit.norm()));
			integers[1][0] = new BigIntegerWrapper(BigInteger.ONE);
			integers[1][1] = new BigIntegerWrapper(BigInteger.ZERO);
			return new NumbersMatrix<BigInteger>(integers);
		}
		catch(Exception e)
		{
			throw new RuntimeException(e);
		}
	}

	private NumbersMatrix<BigInteger> createVector0(IPropertySource ps, Partition partition, BigInteger mod)
	{
		try
		{
			QuadraticFieldGeneralForm unit = QuadraticFieldsInitializer.getGeneralUnit(ps, partition);
			BigIntegerWrapper[][] integers = new BigIntegerWrapper[2][2];
			integers[0][0] = new BigIntegerWrapper(unit.getA().mod(mod));
			integers[0][1] = new BigIntegerWrapper(unit.getB().mod(mod));
			integers[1][0] = new BigIntegerWrapper(BigInteger.ONE);
			integers[1][1] = new BigIntegerWrapper(BigInteger.ZERO);
			return new NumbersMatrix<BigInteger>(integers);
		}
		catch (Exception e)
		{
			throw new RuntimeException(e);
		}
	}

	private NumbersMatrix<BigInteger> createOneMatrix()
	{
		BigIntegerWrapper[][] integers = new BigIntegerWrapper[2][2];
		integers[0][0] = integers[1][1] = new BigIntegerWrapper(BigInteger.ONE);
		integers[0][1] = integers[1][0] = new BigIntegerWrapper(BigInteger.ZERO);
		return new NumbersMatrix<BigInteger>(integers);
	}

	private NumbersMatrix<BigInteger> getVector(IPropertySource ps, Partition partition, BigInteger index, BigInteger mod)
	{
		try
		{
			NumbersMatrix<BigInteger> vector0 = createVector0(ps, partition, mod);
			if (ObjectUtils.equals(BigInteger.ZERO, index))
			{
				return vector0;
			}
			return NumberWrapperUtilities.modPow(createOneMatrix(), createMatrix(ps, partition),index, mod).multiply(vector0).getValue().mod(mod);
		}
		catch (Exception e)
		{
			throw new RuntimeException(e);
		}
	}
}
